{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Best Non-Overlapping Events"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTwoEvents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个最好的不重叠活动"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>events</code>&nbsp;，其中&nbsp;<code>events[i] = [startTime<sub>i</sub>, endTime<sub>i</sub>, value<sub>i</sub>]</code>&nbsp;。第&nbsp;<code>i</code>&nbsp;个活动开始于&nbsp;<code>startTime<sub>i</sub></code>&nbsp;，结束于&nbsp;<code>endTime<sub>i</sub></code>&nbsp;，如果你参加这个活动，那么你可以得到价值&nbsp;<code>value<sub>i</sub></code>&nbsp;。你 <strong>最多</strong>&nbsp;可以参加&nbsp;<strong>两个时间不重叠</strong>&nbsp;活动，使得它们的价值之和 <strong>最大</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回价值之和的 <strong>最大值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>注意，活动的开始时间和结束时间是 <strong>包括</strong>&nbsp;在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 <code>t</code>&nbsp;，那么下一个活动必须在&nbsp;<code>t + 1</code>&nbsp;或之后的时间开始。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/21/picture5.png\" style=\"width: 400px; height: 75px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>events = [[1,3,2],[4,5,2],[2,4,3]]\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"Example 1 Diagram\" src=\"https://assets.leetcode.com/uploads/2021/09/21/picture1.png\" style=\"width: 400px; height: 77px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>events = [[1,3,2],[4,5,2],[1,5,5]]\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>选择活动 2 ，价值和为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/21/picture3.png\" style=\"width: 400px; height: 66px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>events = [[1,5,3],[1,5,1],[6,6,5]]\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= events.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>events[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= startTime<sub>i</sub> &lt;= endTime<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= value<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-best-non-overlapping-events](https://leetcode.cn/problems/two-best-non-overlapping-events/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-best-non-overlapping-events](https://leetcode.cn/problems/two-best-non-overlapping-events/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,2],[4,5,2],[2,4,3]]', '[[1,3,2],[4,5,2],[1,5,5]]', '[[1,5,3],[1,5,1],[6,6,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        q = deque()\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        n = len(events)\n",
    "        f = [0] * n\n",
    "        f[0] = events[0][2]\n",
    "        ret = events[0][2]\n",
    "        for i in range(1, n):\n",
    "            start, event, val = events[i]\n",
    "            l, r = 0, i - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if events[m][1] < start:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            prev = 0 if r == -1 else f[r]\n",
    "            ret = max(ret, prev + val)\n",
    "            f[i] = max(f[i - 1], events[i][2])\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        x, y, res = [0], [0], 0\n",
    "        for i,j,k in events:\n",
    "            res = max(res, k + y[bisect.bisect_left(x,i) - 1])\n",
    "            if j==x[-1]: y[-1] = max(y[-1], k)\n",
    "            elif y[-1]<k:\n",
    "                x.append(j)\n",
    "                y.append(k)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "      events.sort(key = lambda x: x[1])\n",
    "      n = len(events)\n",
    "      ans = events[0][2]\n",
    "      for i in range(1, n):\n",
    "        L, R = 0, i-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if events[mid][1] < events[i][0]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        if L == 0:  ans = max(ans, events[i][2])\n",
    "        else: ans = max(ans, events[i][2] + events[L-1][2])\n",
    "        events[i][2] = max(events[i][2], events[i-1][2])\n",
    "      return ans\n",
    "      \n",
    "      # events.sort(key = lambda x: x[1])\n",
    "      # n = len(events)\n",
    "      # stack = [[0, 0]]\n",
    "      # for start, end, value in events:\n",
    "      #   L, R = 0, len(stack)-1\n",
    "      #   while L <= R:\n",
    "      #     mid = (L + R) // 2\n",
    "      #     if stack[mid][0] < start:   L = mid + 1\n",
    "      #     else: R = mid - 1\n",
    "      #   if end == stack[-1][0]: stack[-1][1] = max(stack[-1][1], value + stack[L-1][1])\n",
    "      #   else: stack.append([end, max(stack[-1][1], value + stack[L-1][1])])\n",
    "      # return stack[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.append([0, 0, 0])\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = max(f[i - 1], events[i][2])\n",
    "        \n",
    "        ans = 0 \n",
    "        for i in range(1, n + 1):\n",
    "            si, ei, vi = events[i]\n",
    "            \n",
    "            l, r = 0, i - 1 \n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1 \n",
    "                if events[mid][1] < si:\n",
    "                    l = mid \n",
    "                else:\n",
    "                    r = mid - 1 \n",
    "            ans = max(ans, f[r] + vi)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # n = len(events)\n",
    "        # events.sort()\n",
    "        # res = mx = 0\n",
    "        # h = []\n",
    "        # for start, end, val in events:\n",
    "        #     while h and h[0][0] < start:\n",
    "        #         mx = max(mx, heappop(h)[1])\n",
    "        #     res = max(res, mx + val)\n",
    "        #     heappush(h, (end, val))\n",
    "        # return res\n",
    "\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        h = []\n",
    "        res = mx = 0\n",
    "        for start, end, val in events[::-1]:\n",
    "            while h and -h[0][0] > end:\n",
    "                mx = max(mx, heappop(h)[1])\n",
    "            res = max(res, mx + val)\n",
    "            heappush(h, (-start, val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "      events.sort(key = lambda x: x[1])\n",
    "      n = len(events)\n",
    "      ans = events[0][2]\n",
    "      for i in range(1, n):\n",
    "        L, R = 0, i-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if events[mid][1] < events[i][0]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        if L == 0:  ans = max(ans, events[i][2])\n",
    "        else: ans = max(ans, events[i][2] + events[L-1][2])\n",
    "        events[i][2] = max(events[i][2], events[i-1][2])\n",
    "      return ans\n",
    "      \n",
    "      # events.sort(key = lambda x: x[1])\n",
    "      # n = len(events)\n",
    "      # stack = [[0, 0]]\n",
    "      # for start, end, value in events:\n",
    "      #   L, R = 0, len(stack)-1\n",
    "      #   while L <= R:\n",
    "      #     mid = (L + R) // 2\n",
    "      #     if stack[mid][0] < start:   L = mid + 1\n",
    "      #     else: R = mid - 1\n",
    "      #   if end == stack[-1][0]: stack[-1][1] = max(stack[-1][1], value + stack[L-1][1])\n",
    "      #   else: stack.append([end, max(stack[-1][1], value + stack[L-1][1])])\n",
    "      # return stack[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "      events.sort(key = lambda x: x[1])\n",
    "      n = len(events)\n",
    "      ans = events[0][2]\n",
    "      for i in range(1, n):\n",
    "        L, R = 0, i-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if events[mid][1] < events[i][0]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        if L == 0:  ans = max(ans, events[i][2])\n",
    "        else: ans = max(ans, events[i][2] + events[L-1][2])\n",
    "        events[i][2] = max(events[i][2], events[i-1][2])\n",
    "      return ans\n",
    "      \n",
    "      # events.sort(key = lambda x: x[1])\n",
    "      # n = len(events)\n",
    "      # stack = [[0, 0]]\n",
    "      # for start, end, value in events:\n",
    "      #   L, R = 0, len(stack)-1\n",
    "      #   while L <= R:\n",
    "      #     mid = (L + R) // 2\n",
    "      #     if stack[mid][0] < start:   L = mid + 1\n",
    "      #     else: R = mid - 1\n",
    "      #   if end == stack[-1][0]: stack[-1][1] = max(stack[-1][1], value + stack[L-1][1])\n",
    "      #   else: stack.append([end, max(stack[-1][1], value + stack[L-1][1])])\n",
    "      # return stack[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        pre = []\n",
    "        ans = 0\n",
    "        for start,end,val in events:\n",
    "            ans = max(ans, val)\n",
    "            \n",
    "            length = len(pre)\n",
    "            for i in range(length-1, -1, -1):\n",
    "                if start > pre[i][0]:\n",
    "                    ans = max(ans, val + pre[i][1])\n",
    "                    break\n",
    "\n",
    "\n",
    "            if pre == []:\n",
    "                pre.append([end,val])\n",
    "            else:\n",
    "                if val <= pre[-1][1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    pre.append([end,val])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        lst1, lst2, lstv = list(zip(*events))\n",
    "        lstv_ = list(accumulate(lstv[::-1], func = max, initial = 0))[::-1]\n",
    "        return max(lstv[i] + lstv_[bisect.bisect(lst1, t2)] for i, t2 in enumerate(lst2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        ans = events[0][2]\n",
    "        stack = [[events[0][1], events[0][2]]]\n",
    "        for st, end, val in events[1:]:\n",
    "            left, right = 0, len(stack)-1\n",
    "            while left <= right:\n",
    "                mid = (left+right) // 2\n",
    "                if stack[mid][0] < st:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans = max(ans, val + stack[right][1] if right >= 0 else val)\n",
    "\n",
    "            if val > stack[-1][1]:\n",
    "                if end == stack[-1][0]:\n",
    "                    stack[-1][1] = val\n",
    "                else:\n",
    "                    stack.append([end, val])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        '''\n",
    "        只能参加两个活动\n",
    "        维护前面活动的最大值，加上这一个活动\n",
    "        '''\n",
    "        events.sort()\n",
    "        h=[]#按照结束时间从小到大排序\n",
    "        pmx=0\n",
    "        ans=0\n",
    "        for s,e,v in events:\n",
    "            while h and h[0][0]<s:\n",
    "                pmx=max(heappop(h)[1],pmx)\n",
    "            ans=max(ans,pmx+v)\n",
    "            heappush(h,(e,v))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        n = len(events)\n",
    "        value = 0\n",
    "        res = 0\n",
    "        pq = []\n",
    "        for start, end, val in events:\n",
    "            heapq.heappush(pq, (end, val))\n",
    "            while pq and pq[0][0] < start:\n",
    "                value = max(value, heapq.heappop(pq)[1])\n",
    "            res = max(res, value+val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        curr_max = 0\n",
    "        q = []\n",
    "        ans = 0\n",
    "\n",
    "        for a, b, c in events:\n",
    "            while q and q[0][0] < a:\n",
    "                _, w = heapq.heappop(q)\n",
    "                if w > curr_max:\n",
    "                    curr_max = w\n",
    "            ans = max(curr_max+c, ans)\n",
    "            heapq.heappush(q, (b, c))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        lst1, lst2, lstv = list(zip(*events))\n",
    "        lstv_ = list(accumulate(lstv[::-1], func = max, initial = 0))[::-1]\n",
    "        return max(lstv[i] + lstv_[bisect_right(lst1, t2)] for i, t2 in enumerate(lst2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        ans, pre = -inf, 0\n",
    "        h = []\n",
    "        for s, e, v in events :\n",
    "            tmp = v\n",
    "            while h and h[0][0] < s :\n",
    "                te, tv = heappop(h)\n",
    "                pre = max(pre, tv)\n",
    "            ans = max(ans, v+pre)\n",
    "            heappush(h, (e, v))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "\n",
    "        h = []\n",
    "        events.sort()\n",
    "        ans = 0\n",
    "        print(events)\n",
    "        val = 0\n",
    "        for i in range(len(events)):\n",
    "            \n",
    "            while h and h[0][0] < events[i][0]:\n",
    "                val = max(val, heappop(h)[1])\n",
    "            ans = max(ans, events[i][2] + val)\n",
    "            # print(val)\n",
    "            # overlapping\n",
    "            heappush(h, (events[i][1], events[i][2]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events = sorted(list(set([tuple(e) for e in events])), key=lambda x: x[2], reverse=True)\n",
    "        # 只选择一个活动的最大值\n",
    "        ans = events[0][2]\n",
    "        n = len(events)\n",
    "        if max(e[0] for e in events) < min(e[1] for e in events):\n",
    "            return ans \n",
    "        for i in range(n):\n",
    "            e1S, e1T, e1V = events[i]\n",
    "            for j in range(i + 1, n):\n",
    "                e2S, e2T, e2V = events[j]\n",
    "                # 此次遍历中最大的两个数值之和小于max, 则直接返回\n",
    "                if e1V + e2V < ans:\n",
    "                    break\n",
    "                # 事件1 排在 事件2之前\n",
    "                if e1S < e2S and e1T < e2S:\n",
    "                    ans = max(ans, e1V+e2V)\n",
    "                elif e2S < e1S and e2T < e1S:\n",
    "                    ans = max(ans, e1V+e2V)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        lst1, lst2, lstv = list(zip(*events))\n",
    "        lstv_ = list(accumulate(lstv[::-1], func = max, initial = 0))[::-1]\n",
    "        return max(lstv[i] + lstv_[bisect.bisect(lst1, t2)] for i, t2 in enumerate(lst2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        ans, pre = -inf, 0\n",
    "        h = []\n",
    "        for s, e, v in events :\n",
    "            while h and h[0][0] < s :\n",
    "                pre = max(pre, heappop(h)[1])\n",
    "            ans = max(ans, v+pre)\n",
    "            heappush(h, (e, v))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        start = sorted(range(n), key=lambda d:events[d][0])\n",
    "        end = sorted(range(n), key=lambda d:events[d][1])\n",
    "\n",
    "        f = [events[start[-1]][2]]\n",
    "        for index in range(n - 2, -1, -1):\n",
    "            f.append(max(f[-1], events[start[index]][2]))\n",
    "        \n",
    "        f.reverse()\n",
    "        \n",
    "        p = 0\n",
    "        res = 0\n",
    "        now = 0\n",
    "        for index in range(n):\n",
    "            while p < n and events[start[p]][0] <= events[end[index]][1]:\n",
    "                p += 1\n",
    "            \n",
    "            if p != n:\n",
    "                res = max(res, events[end[index]][2] + f[p])\n",
    "            else:\n",
    "                res = max(res, events[end[index]][2])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[0])\n",
    "        ans = 0\n",
    "        right_value = 0\n",
    "        # 最小堆\n",
    "        q = []\n",
    "        for event in events:\n",
    "            startTime, endTime, value = event\n",
    "            while q and q[0][0] < startTime:\n",
    "                right_value = max(right_value,heappop(q)[1])\n",
    "            ans = max(ans,value+right_value)\n",
    "            heappush(q,(endTime,value))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda it: it[1])\n",
    "        ans = 0\n",
    "        pre = [-1]\n",
    "        dp = [0]\n",
    "        for a, b, c in events:\n",
    "            dp.append(ac_max(dp[-1], c))\n",
    "            if c > ans:\n",
    "                ans = c\n",
    "            pre.append(b)\n",
    "            i = bisect.bisect_right(pre, a-1)-1\n",
    "            if dp[i] + c > ans:\n",
    "                ans = dp[i]+c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        lst1, lst2, lstv = list(zip(*events))\n",
    "        lstv_ = list(accumulate(lstv[::-1], func = max, initial = 0))[::-1]\n",
    "        return max(lstv[i] + lstv_[bisect.bisect(lst1, t2)] for i, t2 in enumerate(lst2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # endtime=0\n",
    "        # starttime=inf\n",
    "        # map=defaultdict(list)\n",
    "        # for start,end,value in events:\n",
    "        #     map[end].append([start,value])\n",
    "        #     starttime=min(starttime,start)\n",
    "        #     endtime=max(end,endtime)\n",
    "        # # print(endtime)\n",
    "        # ans=0\n",
    "        # dp=[0]*(endtime-starttime+1)\n",
    "        # # print(map)\n",
    "        # for i in range(1,endtime-starttime+1):\n",
    "        #     dp[i]=dp[i-1]\n",
    "        #     if i in map:\n",
    "        #         for start,value in map[i]:\n",
    "        #             dp[i]=max(dp[i],value)\n",
    "        #             ans=max(ans,dp[start-1]+value)\n",
    "        # # print(dp)\n",
    "        # return ans\n",
    "\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        endtime=[ event[1] for event in events]\n",
    "        n=len(events)\n",
    "        dp=[0]*(n+1)\n",
    "        ans=0\n",
    "        # print(events)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=max(dp[i-1],events[i-1][2])\n",
    "            start=events[i-1][0]\n",
    "            idx=bisect.bisect_left(endtime, start)\n",
    "            print(idx)\n",
    "            ans=max(ans,dp[idx]+events[i-1][2])\n",
    "            # print(ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        #排序加优先队列\n",
    "        events.sort(key=lambda x:x[0])#按开始时间排序\n",
    "        que=[]\n",
    "        ans=0\n",
    "        premax=0#记录已遍历数组中最大的val\n",
    "        for start,end,val in events:\n",
    "            while que and que[0][0]<start:#堆顶元素结束时间小于开始时间\n",
    "                premax=max(premax,heappop(que)[1])\n",
    "            ans=max(ans,premax+val)\n",
    "            heappush(que,[end,val])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        res = 0\n",
    "\n",
    "        #----按照l升序排序\n",
    "        events.sort()      \n",
    "\n",
    "        pre_max = 0\n",
    "        minHeap = []\n",
    "        for l, r, val in events:\n",
    "            while minHeap and minHeap[0][0] < l:\n",
    "                pre_max = max(pre_max, minHeap[0][1])\n",
    "                heapq.heappop(minHeap)\n",
    "            res = max(res, pre_max + val)\n",
    "            heapq.heappush(minHeap, (r, val))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        pq = []\n",
    "        maxvalue = ans = 0\n",
    "        events.sort()\n",
    "        for l, r, val in events:\n",
    "            while len(pq) and pq[0][0] < l:\n",
    "                maxvalue = max(maxvalue, heappop(pq)[1])\n",
    "            ans = max(ans, maxvalue + val)\n",
    "            heappush(pq, (r, val))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self,events):\n",
    "        events.sort(key=lambda x: x[0])  # Sort events by start time\n",
    "        heap = []\n",
    "        max_val = 0\n",
    "        ans = 0\n",
    "\n",
    "        for event in events:\n",
    "            start, end, val = event\n",
    "\n",
    "            # Remove events that end before the current event starts\n",
    "            while heap and heap[0][0] < start:\n",
    "                max_val = max(max_val, heapq.heappop(heap)[1])\n",
    "\n",
    "            ans = max(ans, max_val + val)  # Calculate the maximum value for the current event\n",
    "            heapq.heappush(heap, (end, val))  # Push the current event onto the heap\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort()\n",
    "        res = mx = 0\n",
    "        h = []\n",
    "        for start, end, val in events:\n",
    "            while h and h[0][0] < start:\n",
    "                mx = max(mx, heappop(h)[1])\n",
    "            res = max(res, mx + val)\n",
    "            heappush(h, (end, val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x: x[0])\n",
    "        ans, max_val = 0, 0\n",
    "        heap = []\n",
    "        for event in events:\n",
    "            while heap and heap[0][0] < event[0]:\n",
    "                max_val = max(max_val, heappop(heap)[1])\n",
    "            ans = max(ans, max_val + event[2])\n",
    "            heappush(heap, (event[1], event[2]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        ans = 0\n",
    "\n",
    "        #----按照l升序排序\n",
    "        events.sort()      \n",
    "        maxpre = 0\n",
    "        st = []\n",
    "        for e1, e2, vi in events:\n",
    "            while st and st[0][0] < e1:\n",
    "                maxpre = max(maxpre, st[0][1])\n",
    "                heappop(st)\n",
    "            ans = max(ans, maxpre + vi)\n",
    "            heappush(st, (e2,vi)) \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents0(self, events: List[List[int]]) -> int:\n",
    "        # 开始排序, 优先队列\n",
    "        events.sort()\n",
    "        pre_max = 0\n",
    "        q = []\n",
    "        answer = 0\n",
    "\n",
    "        for start, end, value in events:\n",
    "            while q and q[0][0] < start:\n",
    "                pre_max = max(pre_max, heapq.heappop(q)[1])\n",
    "\n",
    "            answer = max(answer, pre_max + value)\n",
    "            heapq.heappush(q, (end, value))\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def maxTwoEvents00(self, events: List[List[int]]) -> int:\n",
    "        # 时间点方法\n",
    "        actions = []\n",
    "\n",
    "        for start, end, value in events:\n",
    "            actions.append((start, 0, value))  # start\n",
    "            actions.append((end, 1, value))  # end\n",
    "\n",
    "        actions.sort()\n",
    "        answer = 0\n",
    "        pre_max = 0\n",
    "\n",
    "        for time, op, value in actions:\n",
    "            if op == 1:  # end\n",
    "                pre_max = max(pre_max, value)\n",
    "            else:\n",
    "                answer = max(answer, pre_max + value)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # 时间点方法\n",
    "        events.sort()\n",
    "        pre_max = 0\n",
    "        ans = 0\n",
    "        q = []\n",
    "\n",
    "        for start, end, value in events:\n",
    "            while q and q[0][0] < start:\n",
    "                pre_max = max(pre_max, q[0][1])\n",
    "                heapq.heappop(q)\n",
    "\n",
    "            ans = max(ans, value + pre_max)\n",
    "            heapq.heappush(q, (end, value))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        # 只参加一次活动能得到的价值\n",
    "        once = 0 \n",
    "        # 缓存当前所有可能参加的活动价值\n",
    "        cache = []\n",
    "        rv = 0\n",
    "        for i,j,k in events:\n",
    "            while len(cache) and cache[0][0]<i:\n",
    "                _, v = heappop(cache)\n",
    "                once = max(once, v)\n",
    "            v = once + k \n",
    "            rv = max(rv,v)\n",
    "            heappush(cache, [j,k])\n",
    "        return rv  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda x:x[0])\n",
    "        q = []\n",
    "        res = 0\n",
    "        max_v = 0\n",
    "        for x, y, v in events:\n",
    "            while q and q[0][0] < x:\n",
    "                max_v = max(max_v, heappop(q)[1])\n",
    "            res = max(res, max_v + v)\n",
    "            heappush(q, (y, v))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[0])\n",
    "        # 维护的是右边的最小值\n",
    "        ans = 0\n",
    "        max_r_v = 0\n",
    "        q = []\n",
    "        # 枚举其中一个活动\n",
    "        for event in events:\n",
    "            startTime, endTime, value = event\n",
    "            while q and startTime > q[0][0]:\n",
    "                max_r_v = max(max_r_v,heappop(q)[1])\n",
    "            ans = max(ans,max_r_v + value)\n",
    "            heappush(q,(endTime,value))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意题目要求参加的两个活动时间上不能连续\n",
    "# 注意题目要求只能参加两个活动\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key = lambda x:x[0]) # 根据活动开始时间由小到大排序\n",
    "        profit = 0 # 记录收益最大值 每次遍历更新比较之前的最大值和参与当前活动的最大值\n",
    "        que = [] # 最小堆 记录每个活动的结束时间和收益 顶部为结束时间最早的活动\n",
    "        biggest = 0 # 记录结束于i开始之前的活动中的最大价值 同时也结束在i之后开始的活动开始之前 \n",
    "        for i in range(1,n+1):# 遍历活动\n",
    "            heapq.heappush(que,(events[i-1][1],events[i-1][2])) # 入堆\n",
    "            while que and que[0][0] < events[i-1][0]: # 在结束早于i开始的活动中比较出最大价值 pop掉\n",
    "                    biggest = max(heapq.heappop(que)[1],biggest)\n",
    "            profit = max(profit, events[i-1][2] + biggest) # 比较不参与i的收益和参加i的收益\n",
    "\n",
    "        return profit\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # 开始排序, 优先队列\n",
    "        events.sort()\n",
    "        pre_max = 0\n",
    "        q = []\n",
    "        answer = 0\n",
    "\n",
    "        for start, end, value in events:\n",
    "            while q and q[0][0] < start:\n",
    "                pre_max = max(pre_max, heapq.heappop(q)[1])\n",
    "\n",
    "            answer = max(answer, pre_max + value)\n",
    "            heapq.heappush(q, (end, value))\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def maxTwoEvents3(self, events: List[List[int]]) -> int:\n",
    "        # 时间点方法\n",
    "        actions = []\n",
    "\n",
    "        for start, end, value in events:\n",
    "            actions.append((start, 0, value))  # start\n",
    "            actions.append((end, 1, value))  # end\n",
    "\n",
    "        actions.sort()\n",
    "        answer = 0\n",
    "        pre_max = 0\n",
    "\n",
    "        for time, op, value in actions:\n",
    "            if op == 1:  # end\n",
    "                pre_max = max(pre_max, value)\n",
    "            else:\n",
    "                answer = max(answer, pre_max + value)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        ans = 0\n",
    "\n",
    "        #----按照l升序排序\n",
    "        events.sort()      \n",
    "        maxpre = 0\n",
    "        st = []\n",
    "        for e1, e2, vi in events:\n",
    "            while st and e1 > st[0][0]:\n",
    "                maxpre = max(maxpre, st[0][1])\n",
    "                heappop(st)\n",
    "\n",
    "            ans = max(ans, maxpre + vi)\n",
    "            heappush(st, (e2, vi))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        sorted_events = sorted([tuple([end + 1, start, value]) for start, end, value in events])\n",
    "        f = [0] * (len(sorted_events) + 1)\n",
    "        ans = 0\n",
    "        for i, (_, start, value) in enumerate(sorted_events):\n",
    "            f[i + 1] = max(f[i], value)\n",
    "            j = bisect_right(sorted_events, (start, inf), hi=i)\n",
    "            ans = max(ans, value + f[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\r\n",
    "        n = len(events)\r\n",
    "        dp = [[0] * 2 for _ in range(n + 1)]\r\n",
    "        # 按照结束时间排序\r\n",
    "        events.sort(key=lambda x:(x[1]))\r\n",
    "        for i in range(n):\r\n",
    "            dp[i + 1][0] = max(dp[i][0], events[i][2])\r\n",
    "            l, r = -1, i\r\n",
    "            while l + 1 < r:\r\n",
    "                mid = (l + r) >> 1 \r\n",
    "                if events[mid][1] >= events[i][0]:\r\n",
    "                    r = mid \r\n",
    "                else:\r\n",
    "                    l = mid\r\n",
    "            dp[i + 1][1] = max(dp[i][1], dp[l + 1][0] + events[i][2])\r\n",
    "        return max(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for e in events:\n",
    "            s, e, v = e[0], e[1], e[2]\n",
    "            evs.append((s, 0, v))\n",
    "            evs.append((e, 1, v))\n",
    "        \n",
    "        evs.sort()\n",
    "\n",
    "        ans = bestfirst = 0\n",
    "\n",
    "        for e in evs:\n",
    "            # 一个开始时间，可以接在一个结束之后\n",
    "            if e[1] == 0:\n",
    "                ans = max(ans, bestfirst + e[2])\n",
    "            else:\n",
    "                bestfirst = max(bestfirst, e[2])\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        envs = []\n",
    "        for x, y, v in events:\n",
    "            envs.append((x, 0, v))\n",
    "            envs.append((y, 1, v))\n",
    "        envs.sort()\n",
    "\n",
    "        ans = 0\n",
    "        maxfirst = 0\n",
    "\n",
    "        for x, flag, v in envs:\n",
    "            if flag == 0:\n",
    "                ans = max(ans, maxfirst + v)\n",
    "            else:\n",
    "                maxfirst = max(maxfirst, v)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents0(self, events: List[List[int]]) -> int:\n",
    "        # 开始排序, 优先队列\n",
    "        events.sort()\n",
    "        pre_max = 0\n",
    "        q = []\n",
    "        answer = 0\n",
    "\n",
    "        for start, end, value in events:\n",
    "            while q and q[0][0] < start:\n",
    "                pre_max = max(pre_max, heapq.heappop(q)[1])\n",
    "\n",
    "            answer = max(answer, pre_max + value)\n",
    "            heapq.heappush(q, (end, value))\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # 时间点方法\n",
    "        actions = []\n",
    "\n",
    "        for start, end, value in events:\n",
    "            actions.append((start, 0, value))  # start\n",
    "            actions.append((end, 1, value))  # end\n",
    "\n",
    "        actions.sort()\n",
    "        answer = 0\n",
    "        pre_max = 0\n",
    "\n",
    "        for time, op, value in actions:\n",
    "            if op == 1:  # end\n",
    "                pre_max = max(pre_max, value)\n",
    "            else:\n",
    "                answer = max(answer, pre_max + value)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        s, e = [], []\n",
    "        l = len(events)\n",
    "        for i in range(l):\n",
    "            s.append((events[i][0], events[i][2]))\n",
    "            e.append((events[i][1], events[i][2]))\n",
    "        s.sort()\n",
    "        e.sort(reverse=True)\n",
    "        ans = 0\n",
    "        a = 0\n",
    "        for x in range(l):\n",
    "            while e and e[-1][0] < s[x][0]:\n",
    "                a = max(a, e.pop()[1])\n",
    "            ans = max(ans, a + s[x][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key= lambda p:p[1])\n",
    "        dp = [[0]*(2+1)  for _ in range (n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            idx = bisect_left(events,events[i-1][0],hi=i-1,key = lambda p : p[1]) -1 \n",
    "            for k in range(1,3):\n",
    "                dp[i][k] = max(dp[i-1][k],dp[idx+1][k-1]+events[i-1][2])\n",
    "        return dp[-1][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        n = len(events)\n",
    "        dp = [[0] * (2+1) for _ in range(n+1)]\n",
    "        for i, (s,e,v) in enumerate(events):\n",
    "            j = bisect_left(events,s,hi = i,key = lambda x:x[1])-1\n",
    "            for k in range(1,2+1):\n",
    "                dp[i+1][k] = max(dp[i][k],dp[j+1][k-1] + v)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        dp = [[0] * 3 for _ in range(len(events))]\n",
    "        for j in range(1, 3):\n",
    "            dp[0][j] = events[0][-1]\n",
    "        # < tar的第一个数\n",
    "        def check(tar):\n",
    "            left = -1\n",
    "            right = len(events) - 1\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "                if events[mid][1] >= tar:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "\n",
    "            return left\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "\n",
    "                idx = check(events[i][0])   \n",
    "                if idx == -1:\n",
    "                    dp[i][j] = max(dp[i][j], events[i][-1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j], dp[idx][j - 1] + events[i][-1])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key=lambda e: e[1])\n",
    "        n = len(events)\n",
    "        f = [[0] * (3) for _ in range(n + 1)]\n",
    "        for i, (start, end, val) in enumerate(events):\n",
    "            p = bisect_left(events, start, hi=i, key=lambda e: e[1])-1  # hi=i 表示二分上界为 i（默认为 n）\n",
    "            for j in range(1, 3):\n",
    "                f[i + 1][j] = max(f[i][j], f[p+1][j - 1] + val)\n",
    "        return f[n][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        n = len(events)\n",
    "        dp = [[0] * 3 for _ in range(n + 1)]\n",
    "        for i,(s,e,v) in enumerate(events):\n",
    "            p = bisect_left(events,s,hi = i,key = lambda x:x[1])\n",
    "            for j in range(1,3):\n",
    "                dp[i+1][j] = max(dp[i][j],dp[p][j-1] + v)\n",
    "        return dp[n][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda x:x[1])\n",
    "        dp = [[0]*3 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1,3):\n",
    "                s,e,v = events[i-1]\n",
    "                if j==1:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+v)\n",
    "                else:\n",
    "                    idx = bisect_left(events, s, key=lambda x:x[1], hi=i-1)\n",
    "                    dp[i][j] = max(dp[i-1][j], v+dp[idx][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        n = len(events)\n",
    "        dp = [[0] * 3 for _ in range(n + 1)]\n",
    "        for i,(s,e,v) in enumerate(events):\n",
    "            p = bisect_left(events,s,hi = i,key = lambda x:x[1]) - 1\n",
    "            for j in range(1,3):\n",
    "                dp[i+1][j] = max(dp[i][j],dp[p+1][j-1] + v)\n",
    "        return dp[n][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: list[list[int]]) -> int:\n",
    "        n = len(events)\n",
    "        events.sort(key=lambda x: x[1])\n",
    "        f = [[0] * 3 for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(1, 3):\n",
    "                l, r = 0, i - 1\n",
    "                while l < r:\n",
    "                    m = l + r + 1 >> 1\n",
    "                    if events[m][1] < events[i][0]:\n",
    "                        l = m\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "                if r >= 0 and events[r][1] < events[i][0]:\n",
    "                    f[i + 1][j] = max(f[i][j], f[r + 1][j - 1] + events[i][2])\n",
    "                else:\n",
    "                    f[i + 1][j] = max(f[i][j], events[i][2])\n",
    "        return f[n][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        events.sort(key = lambda x:x[1])\n",
    "        end_2_event_dict = defaultdict(list)\n",
    "        for event in events:\n",
    "            end_2_event_dict[event[1]].append(event)\n",
    "        \n",
    "        def find_no_lt(end_time):\n",
    "            left, right = 0, len(end_2_max_value_arr) - 1\n",
    "            ans = 0\n",
    "            while left <= right:\n",
    "                middle = (left + right) // 2\n",
    "                if end_2_max_value_arr[middle][0] <= end_time:\n",
    "                    ans = middle\n",
    "                    left = middle + 1\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            return end_2_max_value_arr[ans][1]\n",
    "\n",
    "        last_max = 0\n",
    "        end_2_max_value_arr = [(-1, 0)]\n",
    "        for end in sorted(end_2_event_dict.keys()):\n",
    "            for start,_,value in end_2_event_dict[end]:\n",
    "                ans = max(ans, find_no_lt(start - 1) + value)\n",
    "                last_max = max(last_max, value)\n",
    "            end_2_max_value_arr.append((end, last_max))\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        stack=[]\n",
    "        for s,e,v in events:\n",
    "            stack.append((s,0,v))\n",
    "            stack.append((e,1,v))\n",
    "        stack=sorted(stack,key=lambda x:x[0])\n",
    "        temp,ans,end=0,0,[]\n",
    "        for time,t,value in stack:\n",
    "            if t==0:\n",
    "                ans=max(ans,value)\n",
    "                if end:\n",
    "                    if end[-1][0]<time:\n",
    "                        ans=max(ans,end[-1][1]+value)\n",
    "                    elif len(end)>1:\n",
    "                        ans=max(ans,end[-2][1]+value)\n",
    "            else:\n",
    "                if not end:\n",
    "                    end.append([time,value])\n",
    "                elif end[-1][0]==time:\n",
    "                    end[-1][1]=max(end[-1][1],value)\n",
    "                else:\n",
    "                    end.append([time,max(value,end[-1][1])])\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        stack=[]\n",
    "        for s,e,v in events:\n",
    "            stack.append((s,0,v))\n",
    "            stack.append((e,1,v))\n",
    "        stack=sorted(stack,key=lambda x:x[0])\n",
    "        temp,ans,end=0,0,[]\n",
    "        for time,t,value in stack:\n",
    "            if t==0:\n",
    "                ans=max(ans,value)\n",
    "                if end:\n",
    "                    if end[-1][0]<time:\n",
    "                        ans=max(ans,end[-1][1]+value)\n",
    "                    elif len(end)>1:\n",
    "                        ans=max(ans,end[-2][1]+value)\n",
    "            else:\n",
    "                if not end:\n",
    "                    end.append([time,value])\n",
    "                elif end[-1][0]==time:\n",
    "                    end[-1][1]=max(end[-1][1],value)\n",
    "                else:\n",
    "                    end.append([time,max(value,end[-1][1])])\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        sorted_events = sorted([tuple([end + 1, start, value]) for start, end, value in events])\n",
    "        f = [[0] * 3 for _ in range(len(sorted_events) + 1)]\n",
    "        for i, (_, start, value) in enumerate(sorted_events):\n",
    "            j = bisect_right(sorted_events, (start, inf), hi=i)  #上一个会议最迟时刻\n",
    "            for t in range(0, 2):\n",
    "                f[i + 1][t + 1] = max(f[i][t + 1], f[j][t] + value)\n",
    "        return max(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        activities = []\n",
    "        for e in events:\n",
    "            activities.append((0, e[0], e[2]))\n",
    "            activities.append((1, e[1], e[2]))\n",
    "        activities.sort(key=lambda elem: (elem[1], elem[0]))\n",
    "        ans = 0\n",
    "        best_first = None\n",
    "        for i, (op, t, val) in enumerate(activities):\n",
    "            if op == 1:\n",
    "                if best_first is None:\n",
    "                    best_first = i\n",
    "                elif activities[best_first][2] < val:\n",
    "                    best_first = i\n",
    "            else:\n",
    "                ans = max(ans, (activities[best_first][2] if best_first and activities[best_first][1] < t else 0) + val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self, ts: int, op: int, val: int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self, other: \"Event\") -> bool:\n",
    "        return (self.ts, self.op) < (other.ts, other.op)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0], 0, event[2]))\n",
    "            evs.append(Event(event[1], 1, event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        ans = bestFirst = 0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                ans = max(ans, ev.val + bestFirst)\n",
    "            else:\n",
    "                bestFirst = max(bestFirst, ev.val)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = []\n",
    "        for i in events:\n",
    "            evs.append([i[0],0,i[2]])\n",
    "            evs.append([i[1],1,i[2]])\n",
    "        evs.sort(key=lambda x: (x[0], x[1]))\n",
    "\n",
    "        first = ans = 0\n",
    "        for i in evs:\n",
    "            if i[1] == 0:\n",
    "                ans = max(ans, first + i[2])\n",
    "            else:\n",
    "                first = max(first, i[2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self, ts: int, op: int, val: int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self, other: \"Event\") -> bool:\n",
    "        return (self.ts, self.op) < (other.ts, other.op)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0], 0, event[2]))\n",
    "            evs.append(Event(event[1], 1, event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        ans = bestFirst = 0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                ans = max(ans, ev.val + bestFirst)\n",
    "            else:\n",
    "                bestFirst = max(bestFirst, ev.val)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        # events.sort(key=lambda x: (x[1],-x[0],-x[2]))\n",
    "        # res = events[0][-1]\n",
    "        # for i in range(1,len(events)):\n",
    "        #     maxv = 0\n",
    "\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         if events[j][1]<events[i][0]:\n",
    "        #             maxv = max(events[j][2],maxv)\n",
    "        #     res = max(res,events[i][2]+maxv)\n",
    "        # return res\n",
    "\n",
    "        e = []\n",
    "        for start,end,value in events:\n",
    "            e.append([start,value,0])\n",
    "            e.append([end,value,1])\n",
    "        e.sort(key=lambda x:(x[0],x[2],x[1]))\n",
    "        prevmax = 0\n",
    "        res = 0\n",
    "        for _,val,is_end in e:\n",
    "            if is_end:\n",
    "                prevmax = max(prevmax,val)\n",
    "            else:\n",
    "                res=max(res,prevmax+val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self,ts:int,op:int,val:int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self,other:'Event'):\n",
    "        return (self.ts,self.op)<(other.ts,other.op)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0],0,event[2]))\n",
    "            evs.append(Event(event[1],1,event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        ans=pre=0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                ans = max(ans,pre+ev.val)\n",
    "            else:\n",
    "                pre = max(pre,ev.val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self,ts:int,op:int,val:int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self,other:'Event'):\n",
    "        return (self.ts,self.op)<(other.ts,other.op)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0],0,event[2]))\n",
    "            evs.append(Event(event[1],1,event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        res=tmp=0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                res = max(res,tmp+ev.val)\n",
    "            else:\n",
    "                tmp = max(tmp,ev.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self, ts: int, op: int, val: int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self, other: \"Event\") -> bool:\n",
    "        return (self.ts, self.op) < (other.ts, other.op)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0], 0, event[2]))\n",
    "            evs.append(Event(event[1], 1, event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        ans = bestFirst = 0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                ans = max(ans, ev.val + bestFirst)\n",
    "            else:\n",
    "                bestFirst = max(bestFirst, ev.val)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Event:\n",
    "    def __init__(self,ts:int,op:int,val:int):\n",
    "        self.ts = ts\n",
    "        self.op = op\n",
    "        self.val = val\n",
    "    \n",
    "    def __lt__(self,other:'Event'):\n",
    "        return (self.ts,self.op)<(other.ts,other.op)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        evs = list()\n",
    "        for event in events:\n",
    "            evs.append(Event(event[0],0,event[2]))\n",
    "            evs.append(Event(event[1],1,event[2]))\n",
    "        evs.sort()\n",
    "\n",
    "        cur=pre=0\n",
    "        for ev in evs:\n",
    "            if ev.op == 0:\n",
    "                cur = max(cur,pre+ev.val)\n",
    "            else:\n",
    "                pre = max(pre,ev.val)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTwoEvents(self, events: List[List[int]]) -> int:\n",
    "        events.sort()\n",
    "        lefts = [x for x, y, v in events]\n",
    "        @cache\n",
    "        def f(i, s):\n",
    "            if s >= 2 or i >= len(events):\n",
    "                return 0\n",
    "            ans = f(i+1, s)\n",
    "            l, r, v = events[i]\n",
    "            j = bisect_left(lefts, r+1)\n",
    "            ans = max(ans, v + f(j, s+1))\n",
    "            return ans\n",
    "        \n",
    "        return f(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
